1. Field of the Invention
The invention relates to a system for and a method of determining the order of departure (or of service) of temporarily stored information or objects.
It relates in particular to the evacuation of a flow of information or objects arriving at a particular location where they are stored temporarily and from which they must be evacuated in an order that depends on various criteria.
Such evacuation or xe2x80x9cservicexe2x80x9d gives rise to difficult problems, in particular if the incoming bit rate and the evacuation bit rate are high.
These problems arise more particularly in telecommunication networks in which digital information signals are transmitted in the form of cells or packets and are stored temporarily in buffers. The cells or packets support calls with different grades of service and it is therefore standard practice to allocate them different bit rates and different relative priorities of service. To control the output of packets or cells from the buffer according to their relative priority, the order of service (or evacuation) of the packets or cells in the buffer must therefore be determined continuously.
Similar problems of establishing an order of distribution can also arise in other technical fields, for example aircraft arriving at and departing from an airport or trains arriving at and departing from a train station.
Generally speaking, buffer service disciplines are classified into two categories according to the time at which the order of service is determined, namely:
first-in-first-out (FIFO) queues, in which the order of service is determined when the packets or cells arrive at the buffer, and
schedulers, in which the order of service is determined when the packets or cells depart from the buffer.
2. Description of the Prior Art
U.S. Pat. No. 4,005,391 describes a system for determining the interrupt priority order of a processor which several peripheral devices can access, but not simultaneously. The values of the interrupt request signals to be processed are stored in an input-output device. The priority information is stored in the elements of a memory: the position of a bit at 1 in a series of bits at 0 determines the service priority for a peripheral device. The address counter scans the content of the buffer to transcode, as it were, the regularly incremented value supplied by the counter. The buffer has eight outputs, only one of which supplies the value 1, the content of the memory being chosen so that all the peripheral devices have different priority levels. Each output of the memory supplies the value 1 in succession to enable AND gates in succession.
An AND gate enabled at one input transmits any interrupt request that it receives on its other input. Scanning is stopped as soon as an AND gate has transmitted an active interrupt request signal. This scanning enables the interrupt requests to be considered in succession and in a particular priority order by enabling gates in succession, but there is no provision for defining the priorities dynamically.
The present invention relates to a scheduler which continuously takes account of the respective relative priorities of the various packets or cells stored in the buffer of an ATM switch, for example.
The order of service is determined in a scheduler of this kind by a selection algorithm taking account of time parameters associated with the packets or cells stored in the buffer. Until now these time parameters have been managed using either random access memory organized in the form of tables or chained lists or content-addressable memory. The processing times of such systems can be incompatible with operation at high bit rates, when the time allocated to each service is very short.
The invention provides a system which can schedule dynamically and very fast.
For simplicity, in the following description, the term xe2x80x9cobjectxe2x80x9d is sometimes used to refer to information or an object processed in the system.
The invention provides a system for determining an order of service of temporarily stored objects, at least one priority flag being attached to certain objects, the system including:
a set of storage units disposed in a matrix organized into C subsets of elements, where C is the number of objects stored temporarily, each of said subsets corresponding to an object and all the subsets including the same number P of elements corresponding to P time positions, each element including a memory which can receive at least one time priority flag, and
first time position selector means for determining, within the matrix, and from all the subsets, the element(s) marked by a particular time priority flag and corresponding to the time position having the lowest value, and
means for writing a time priority flag for a given object into a random access memory element corresponding to a time position allocated to that object.
The priority flags can therefore be written dynamically into a matrix of storage elements, each row corresponding to a subset, for example, i.e. to an object, and each column to a particular time position. The highest priority is assigned to the row(s) with an element containing a priority flag whose flag is at the lowest rank.
In one embodiment, object priority selector means are provided for selecting, in the matrix, only one of the subsets preselected by the first time position selector means. Alternatively, a predetermined number of objects to be serviced simultaneously is selected from the objects that have been preselected.
In these embodiments, the system includes object priority selector means for selecting at least one of the subsets preselected by the first time position selector means.
In one embodiment, to allow for the advancing clock time, at each clock time an offset of one time position is introduced between the time priority flags of each subset and the rank corresponding to their time position so that their new rank corresponds to the next lower time position.
The offset by one time position is effected at the end of each object service time if the service is periodic at each clock time. This time position shift is effected, for example, by transferring the content of the memory of each element to the next element corresponding to the next lower time position.
Alternatively, the contents of the memories of the elements are not modified but instead their ranks are shifted, each rank of an element being reduced by one unit.
In one embodiment, the object priority selector means are connected to the memory elements by means of one incoming conductor per subset transmitting a selected object signal and effect the final choice of at least one object to be serviced from the objects corresponding to the subsets transmitting a selected object signal.
In one embodiment, the first time position selector means are connected to the memory elements by two common conductors for each of the P time positions, namely an incoming common conductor for receiving a time position signal that is a candidate for selection, and an outgoing common conductor for transmitting a retained time position signal. In this case, the first time position selector means identify, among the P signals received on the incoming common conductors, the first time position signal which is a candidate for selection corresponding to the time position having the smallest value and indicate the selected first time position by transmitting a retained time position signal on the outgoing common conductor corresponding to the selected first time position.
In one embodiment, for each subset, the time position of the element containing a time priority flag represents the required time of servicing the object corresponding to that subset relative to the other objects, the first time position selector means giving priority to selecting the object(s) whose priority flag is in an element corresponding to the time position with the lowest value.
In one embodiment, each memory element:
activates the corresponding incoming common conductor of the first time position selector means to transmit thereto a time position signal which is a candidate for selection if the time priority flag is marked in its memory,
receives from the first time position selector means, over an outgoing common conductor for each time position, a retained time position signal if the first time position selector means indicate that the time position of that element has been selected, and
generates, on one common conductor per subset, a selected object signal addressed to the priority object selector means, if, simultaneously:
the time priority flag is marked in its memory, and
the retained time position signal is received from the outgoing common conductor of the first time position selector means.
In one embodiment, a time priority flag for each subset represents the required latest time for servicing the object.
In one embodiment, one or both of the following two additional priority flags is or are added to each subset:
a flag of the earliest authorized selection time position before which the object cannot be serviced, the flag having a time position of smaller value than that of the flag representing the latest required time for service, and
a flag of the optimum selection time position for service, the time position of the flag having a value less than that of the flag of the lost required time for service, and, if these two additional priority flags are present simultaneously, the optimum selection time position flag has a value which is greater than that of the earliest authorized selection flag before which the object cannot be serviced.
If the additional two priority flags are present simultaneously, the optimum selection time position flag has a value higher than that of the earliest authorized selection flag before which the object cannot be serviced.
In one embodiment, a plurality of different type time priority flags is attached to each subset and the system includes a number of flag element matrices equal to the number of types of flag.
In one embodiment, a plurality of flags of different types is allocated to each subset, each element includes a number of memory points at least equal to the number of types of flag and each memory point is allocated to a flag of a particular type.
In one embodiment, the system includes flag search means which, during a first phase, search each subset for the first time priority flag which, of all the flags of the subset, has the time position of the highest value, and after preselecting the subsets which have the first time position flag of the lowest value, during a second phase, the subsequent flags of lower time position in the preselected subsets are searched for and the subsets are selected which have a subsequent flag at the lowest time position.
In one embodiment:
each element stores a single priority flag,
a lost time flag, an earliest authorized selection flag and an optimum time flag are allocated to each subset, the flags corresponding in each subset to different time positions,
the object priority selector means include additional means for generating a time priority flag search signal for each of the subsets whose earliest authorized selection flag has reached the object priority selector means on going beyond the lowest time position to reach the time position of the server, and
the first time position selector means include additional means for effecting two successive phases of selection of other priority flags, first by preselecting the object(s) whose time position of the latest time flag has the lowest value, and then by selecting, from the preselected subsets, the object(s) whose time position of the optimum time flag has the lowest value.
In one embodiment, the object priority selector means further include, for each subset, a memory in which are stored:
an authorized selection indication as soon as the time position of the authorized selection priority flag has reached the time position of the server, and
an optimum position reached indication as soon as the time position of the optimum position priority flag has reached the time position of the server.
In one embodiment, the object priority selector means are connected to each subset of the matrix of elements by:
an outgoing conductor connected to the element of the subset that corresponds to the time position having the highest value, enabling it to generate, for the corresponding subset, a flag search activation signal for initiating an operation searching for a first flag to be selected as a matter of priority in the subset, and
an incoming conductor from the element of the subset that corresponds to the time position having the lowest value, enabling it to receive a selected object signal and to effect the final choice of at least one object to be serviced from the subsets from which it receives a selected object signal.
In one embodiment, each storage element is connected:
to the element of the same subset corresponding to the next higher time position, via a flag search input for receiving a flag search signal, the element of the subset having the time position with the highest value receiving a flag search signal supplied by the object priority selector means, and
to the memory element of the same subset corresponding to the next lower time position, via a flag search output for transmitting a flag search signal, the element having the lowest time position value supplying the flag search signal to the object priority selector means, which signal, if it is active, signifies a selected object signal for those means.
In addition, in this embodiment each memory element:
activates the corresponding incoming common conductor of the time selector means to transmit thereto a time position signal which is a candidate for selection if, simultaneously, an active flag search signal is received and the time priority flag is marked in the memory of the element,
activates an unselected local priority flag signal if, simultaneously:
an active flag search signal is received,
a time priority flag is marked in its memory, and
no retained time position signal is received from the outgoing common conductor of the time selection means, and
retransmits to the element of the same subset which has the next lower time position a flag search signal which is active if, simultaneously:
an active flag search signal is received, and
either the element has no time priority flag marked in its memory,
or the element has a time priority flag marked in its memory and the unselected local priority flag signal is not active, the effect of the unselected local priority flag signal then being to block the propagation of the flag search signal to the other elements of the subset of lower rank if the element has transmitted a time position signal which is a candidate for selection to the time selector means but the means have not returned a retained time position signal.
The invention also relates to application of the above system to managing cells or packets of digital signals in a telecommunication system buffer which cells or packets enter and leave at a high frequency.
Other features and advantages of the invention will become apparent in the course of the following description of some embodiments of the invention, which is given with reference to the accompanying drawings.